import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

// 插入、删除和获取随机元素O(1)时间的结构
// 测试链接 : https://leetcode.cn/problems/insert-delete-getrandom-o1/
public class InsertDeleteRandom {

    class RandomizedSet {
        public HashMap<Integer,Integer> map;
        public ArrayList<Integer> list;

        public RandomizedSet() {
            map = new HashMap<>();
            list = new ArrayList<>();
        }

        public boolean insert(int val) {
            if(map.containsKey(val)){  //已经有了就不用插入了
                return false;
            }
            int size = list.size(); //查询当前可以放置该数的下标
            map.put(val,size);
            list.add(val);
            return true;
        }

        public boolean remove(int val) {
            if(!map.containsKey(val)) {
                return false;            //没有则无法删除
            }
            int valIndex = map.get(val);
            int endVal = list.get(list.size()-1);
            map.put(endVal,valIndex);
            list.set(valIndex,endVal);
            map.remove(val);
            list.remove(list.size()-1);
            return true;
        }

        public int getRandom() {

            return list.get((int) (Math.random()) * list.size() );  //获取数组[0-size)上的随机元素
        }

    }
}
